/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-13
 * Time: 22:51
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class Solution {
    public int countNodes(TreeNode root) {
        // 求左子树的高度
        TreeNode left = root;
        int hl = 0;
        while (left != null) {
            left = left.left;
            hl++;
        }
        // 求右子树的高度
        TreeNode right = root;
        int hr = 0;
        while (right != null) {
            right = right.right;
            hr++;
        }
        // 如果高度相同说明是满二叉树, 按照公式计算出结果
        if (hl == hr) {
            return (int)Math.pow(2, hl) - 1;
        }
        // 高度不相同, 就按照求普通二叉树高度的方法求
        // 左右只有一个不是满二叉树, 所以最终的时间复杂度为 logn  * logn
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
